package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import lombok.extern.slf4j.Slf4j;


/**
 * https://www.runoob.com/w3cnote/counting-sort.html
 */
@Slf4j
public class Sort7_计数排序 implements IAS {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 获取最大与最小
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 索引为arr的值，值为arr中元素出现的个数
        int[] tmp = new int[max - min + 1];
        // 填充数据为0
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = 0;
        }

        // 防止负数，索引增加因子
        int far = 0 - min;

        // 累加次数
        for (int i = 0; i < arr.length; i++) {
            int k = arr[i] + far;
            int v = tmp[k] + 1;
            tmp[k] = v;
        }

        // 修改原数组
        int idx = 0;
        for (int k = 0; k < tmp.length; k++) {
            int count = tmp[k];
            for (int j = 0; j < count; j++) {
                arr[idx] = k - far;
                idx++;
            }
        }

    }
}
